#include<bits/stdc++.h>

using namespace std;
using ll = long long;
#define endl '\n'

#define REP(i, x, y) for (auto i = (x), _##i = (y); i < _##i; ++i)
#define PER(i, x, y) for (auto i = (x), _##i = (y); i > _##i; --i)

template<class T=int>
inline void OO(const T &coll, const char *del = ",") {
    copy(coll.begin(), coll.end(), ostream_iterator<decltype(*coll.begin())>(cerr, del));
    cerr << endl;
}

//记忆化搜索
int dp[100000];
int a[] = {100,50,20,10, 5, 4, 2, 1};

int f(int x) {
    if (dp[x] != 0)return dp[x];//先查表

    if (find(a, a + 5, x) != a + 5) {


        return dp[x] = 1;//写入答案
    }
    int best = x;
    for (int i = 0; i < 5; i++) {
        if (x >= a[i])
            best = min(best, 1 + f(x - a[i]));
    }

    return  dp[x] = best;//及时写入答案，方便下次调用


}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // cout << f(800) << endl;
    copy(dp, dp + 10, ostream_iterator<int>(cerr, " "));
    cerr << endl;

    f(13);

    copy(dp, dp + 10, ostream_iterator<int>(cerr, " "));
    cerr << endl;
    cout << f(15) << endl;
    return 0;
}
